package com.study.algorithm.base.list;

import com.study.algorithm.base.common.ListUtil;

import java.util.Arrays;

/**
 * FastSort
 *
 * @author wanghuilong
 * @version 1.0
 * @description fast sort
 * @date 2023/1/25 18:19
 */
public class FastSort {

    public static void main(String[] args) {
        int[] arr = new int[]{7,1,3,4,2,5,0};
        spiltByNum(arr,5);
        System.out.println(Arrays.toString(arr));
        arr = new int[]{7,1,3,4,2,5,0};
        spiltByNum2(arr,4);
        System.out.println(Arrays.toString(arr));
        arr = new int[]{7,1,3,4,2,5,0};
        fastSortV1(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));
        arr = new int[]{7,1,3,4,2,5,0};
        fastSortV2(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * split the array for two parts by estimate the item of array
     * , if it less or equal the num then put to the left of  array
     * , then put the other items put to the right of  array
     * @param arr
     * @param num
     */
    public static void spiltByNum(int[] arr , int num) {
        int lessOrEqualIndex = -1;
        int i = 0;
        while (lessOrEqualIndex < arr.length && i < arr.length) {
            if(arr[i] <= num) {
                lessOrEqualIndex++;
                ListUtil.swap(arr, lessOrEqualIndex, i);
            }
            i++;
        }
    }


    /**
     * split the array for three parts by estimate the item of array
     * , if the item less or equal the num then put to the left of array
     * , if the item equals to the num then put to the middle of array
     * , then put the other items put to the right of  array
     * @param arr
     * @param num
     */
    public static void spiltByNum2(int[] arr , int num) {
        int lessIndex = -1;
        int biggerIndex = arr.length;
        int i = 0;
        while ( i < biggerIndex) {
            if(arr[i] < num) {
                lessIndex++;
                ListUtil.swap(arr, lessIndex, i);
                i++;
            }else if(arr[i] > num){
                biggerIndex--;
                ListUtil.swap(arr, biggerIndex, i);
            }else {
                i++;
            }
        }
    }


    public static void fastSortV1(int[] arr,int startIndex,int endIndex) {
        if(startIndex == endIndex) {
            return;
        }
        int middleValue = arr[endIndex] ;
        int lessIndex = startIndex - 1;
        int i = startIndex;
        while(i <= endIndex && lessIndex <= endIndex) {
            if(arr[i] <= middleValue) {
                lessIndex++;
                ListUtil.swap(arr, lessIndex, i);
            }
            i++;
        }
        if(lessIndex > startIndex) {
            fastSortV1(arr,startIndex,lessIndex - 1);
        }
        if(endIndex > lessIndex) {
            fastSortV1(arr,lessIndex + 1,endIndex);
        }
    }


    public static void fastSortV2(int[] arr,int startIndex,int endIndex) {
        if(startIndex == endIndex) {
            return;
        }
        int middleValue = arr[endIndex];
        int lessIndex = startIndex - 1;
        int bigIndex = endIndex + 1;
        int i = startIndex;
        while(i < bigIndex) {
            if(arr[i] < middleValue) {
                lessIndex++;
                ListUtil.swap(arr, lessIndex, i);
                i++;
            }else if(arr[i] > middleValue){
                bigIndex--;
                ListUtil.swap(arr, bigIndex, i);
            }else {
                i++;
            }
        }
        if(lessIndex > startIndex) {
            fastSortV2(arr,startIndex,lessIndex);
        }
        if(endIndex > bigIndex) {
            fastSortV2(arr,bigIndex,endIndex);
        }
    }



}
